package datastructure.str;

/**
 * 实现 strStr()
 */
public class LC28 {
    public static int strStr(String haystack, String needle) {
        int n = haystack.length(), m = needle.length();
        if (m == 0) {
            return 0;
        }
        //构造模式串的前缀表，也就是needle的前缀表
        int[] pi = new int[m];
        //将j作为左指针，i作为右指针，每次判断i是否等于j， j的定义是最长相等前后缀的长度
        /**
         * a        j=0
         * ab       j=0
         * abc      j=0
         * abcd     j=0
         * abcda    j=1  第一个a和最后一个a相等
         * abcdab   j=2  第一个ab和最后一个ab
         * abcdabc  j=3  abc 和 abc
         * abcdabcy j=0  前缀中不包含y，后缀包含y，所以找不到相等的前后缀
         * abcdabca j=1  这样的话就是第一个a和最后一个a， 因为后缀最后一个字母是a，在前缀中找不到其他最后一个字母是a并且前面的部分也等于后缀部分的
         * abcdabcy的前缀表为[0,0,0,0,1,2,3,0]
         * abcdabca的前缀表为[0,0,0,0,1,2,3,1]
         */
        for (int j = 0, i = j + 1; i < m; i++) {
            while (j > 0 && needle.charAt(i) != needle.charAt(j)) {
                j = pi[j - 1];
            }
            if (needle.charAt(i) == needle.charAt(j)) {
                j++;
            }
            pi[i] = j;
        }
        //开始遍历原文本
        /**
         * 模式串abcdabcy的前缀表为[0,0,0,0,1,2,3,0]
         * 从文本串和模式串的第一个字符开始匹配，如果相等则下标都+1
         * 如果不相等，则模式串的指针需要指向当前指针对应的前缀表的前一个元素的值作为下标
         * 当j遍历完模式串的最后一个元素时，说明匹配完成
         */
        for (int i = 0, j = 0; i < n; i++) {
            while (j > 0 && haystack.charAt(i) != needle.charAt(j)) {
                j = pi[j - 1];
            }
            if (haystack.charAt(i) == needle.charAt(j)) {
                j++;
            }
            if (j == m) {
                return i - m + 1;
            }
        }
        return -1;
    }
}